「Luogu P4396」[AHOI2013]作业 解题报告

题面

解题思路

莫队+树状数组

分析

区间操作，不带修改，食用莫队大法，然后莫队过程中用树状数组记录每个数出现的次数即可

当然，要记录两个信息，一个是个数，一个是种类数，最后查询即可

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int l,r,x,y,i;
}b[N];
int n,m,pos[N],Ans1[N],Ans2[N],fx[N<<2],fy[N<<2],block,l,r,sum[N<<2],a[N];
inline bool cmp(rgt node a,rgt node b) {
    return (pos[a.l]^pos[b.l])?a.l<b.l:(pos[a.l]&1)?a.r<b.r:a.r>b.r;
}
inline void Modify(rint p,rint x,rint y) {//两个数组
    if(p) for(;x<=n;x+=x&(-x)) fx[x]+=y;
    else for(;x<=n;x+=x&(-x)) fy[x]+=y;
}
inline void Add(rint x) {
    if(!sum[x]) Modify(0,x,1);
    ++sum[x],Modify(1,x,1);
}
inline void Del(rint x) {
    --sum[x],Modify(1,x,-1);
    if(!sum[x]) Modify(0,x,-1);
}
inline void Query(rint i,rint l,rint r) {
    rint x,y;x=y=0;
    for(;r;r-=r&(-r)) x+=fx[r],y+=fy[r];
    for(;l;l-=l&(-l)) x-=fx[l],y-=fy[l];
    Ans1[i]=x,Ans2[i]=y;
}
int main()
{
    rint i,j;
    n=read(),m=read(),block=pow(n,0.54);
    for(i=1;i<=n;i++) a[i]=read(),pos[i]=i/block;
    for(i=1;i<=m;i++) b[i].l=read(),b[i].r=read(),b[i].x=read(),b[i].y=read(),b[i].i=i;
    sort(b+1,b+m+1,cmp),l=1;
    for(i=1;i<=m;i++) {
        while(r<b[i].r) Add(a[++r]);
        while(l>b[i].l) Add(a[--l]);
        while(r>b[i].r) Del(a[r--]);
        while(l<b[i].l) Del(a[l++]);
        Query(b[i].i,b[i].x-1,b[i].y);//最后查询
    }
    for(i=1;i<=m;i++) printf("%d %d\n",Ans1[i],Ans2[i]);
    return 0;
}

强弱化版 Luogu P4867 Gty的二逼妹子序列（既强又弱）

正解值域分块，但是不知道为什么普通莫队过掉了

分析

普通莫队+树状数组的复杂度是 $O(m\sqrt n\log n)$，但是由于数据水跑不满，虽说如此，还是可以看出其的稳定性不是很优，$author$ 亲测最坏时间 $2.66s$，另一个较大的点却跑了 $923ms$

相较之下，值域分块的复杂度为 $O(m\sqrt n)$，更加稳定且正确，两个测试点分别跑了 $1.60s$ 和 $1.18s$

树状数组 $version$：

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 1000007
#define N 100007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int l,r,a,b,i;
}b[M];
int n,m,l,r,block,a[N],f[N],sum[N],pos[N],Ans[M];
inline bool cmp(rgt node a,rgt node b) {
    return (pos[a.l]^pos[b.l])?a.l<b.l:(pos[a.l]&1)?a.r>b.r:a.r<b.r;
}
inline void Modify(rint x,rint p) {
    if(p) for(;x<=n;x+=x&(-x)) ++f[x];
    else for(;x<=n;x+=x&(-x)) --f[x];
}
inline int Query(rint l,rint r) {
    rint res=0;
    for(;r;r-=r&(-r)) res+=f[r];
    for(;l;l-=l&(-l)) res-=f[l];
    return res;
}
inline void Add(rint x) {if(!sum[x]++) Modify(x,1);}
inline void Del(rint x) {if(!--sum[x]) Modify(x,0);}
int main()
{
    rint i,j;
    n=read(),m=read(),block=n/(sqrt(0.9*m)+1);
    for(i=1;i<=n;i++) a[i]=read(),pos[i]=i/block;
    for(i=1;i<=m;i++) b[i].l=read(),b[i].r=read(),b[i].a=read(),b[i].b=read(),b[i].i=i;
    sort(b+1,b+m+1,cmp),l=1;
    for(i=1;i<=m;i++) {
        while(r<b[i].r) Add(a[++r]);
        while(l>b[i].l) Add(a[--l]);
        while(r>b[i].r) Del(a[r--]);
        while(l<b[i].l) Del(a[l++]);
        Ans[b[i].i]=Query(b[i].a-1,b[i].b);
    }
    for(i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}

值域分块 $version$：

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 1000007
#define N 100007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int l,r,a,b,i;
}b[M];
int n,m,l,r,block,a[N],f[N],sum[N],pos[N],Ans[M],L[N],R[N],ans[N],num;
inline bool cmp(rgt node a,rgt node b) {
    return (pos[a.l]^pos[b.l])?a.l<b.l:(pos[a.l]&1)?a.r>b.r:a.r<b.r;
}
inline int Query(rint l,rint r) {
    rint res=0;
    if(pos[l]==pos[r]) {
        while(l<=r) res+=(sum[l]>0),++l;
        return res;
    }rint i;
    for(i=l;i<=R[pos[l]];i++) res+=(sum[i]>0);
    for(i=L[pos[r]];i<=r;i++) res+=(sum[i]>0);
    for(i=pos[l]+1;i<pos[r];i++) res+=ans[i];
    return res;
}
inline void Add(rint x) {if(!sum[x]++) ans[pos[x]]++;}
inline void Del(rint x) {if(!--sum[x]) ans[pos[x]]--;}
int main()
{
    rint i,j;
    n=read(),m=read(),block=n/(sqrt(0.9*m)+1);
    for(i=1;i<=n;i++)
        a[i]=read(),pos[i]=(i-1)/block+1;
    num=(n-1)/block+1,R[num]=n,L[num]=block*(num-1)+1;
    for(i=1;i<num;i++) L[i]=block*(i-1)+1,R[i]=block*i;
    for(i=1;i<=m;i++) b[i].l=read(),b[i].r=read(),b[i].a=read(),b[i].b=read(),b[i].i=i;
    sort(b+1,b+m+1,cmp),l=1;
    for(i=1;i<=m;i++) {
        while(r<b[i].r) Add(a[++r]);
        while(l>b[i].l) Add(a[--l]);
        while(r>b[i].r) Del(a[r--]);
        while(l<b[i].l) Del(a[l++]);
        Ans[b[i].i]=Query(b[i].a,b[i].b);
    }
    for(i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}